package uestc.lj.advanced.dp;

/**
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code10_SplitNumber {

	public static int splitNumber1(int n) {
		if (n < 1) {
			return 0;
		}
		return process1(1, n);
	}

	/**
	 * 在大于等于pre的前提下，裂开rest所需要的方法数
	 *
	 * @param pre  之前裂开的部分
	 * @param rest 还剩下多少需要裂开
	 * @return 方法数
	 */
	private static int process1(int pre, int rest) {
		if (rest == 0) {
			// 之前裂开的方法构成了1种有效方法
			return 1;
		}
		if (pre > rest) {
			// 必须递增的裂开
			return 0;
		}
		int way = 0;
		for (int i = pre; i <= rest; i++) {
			way += process1(i, rest - i);
		}
		return way;
	}

	//================================================================

	public static int splitNumber2(int n) {
		if (n < 1) {
			return 0;
		}
		// dp[i][j]表示 在i的前提下，还剩下j需要裂开
		int[][] dp = new int[n + 1][n + 1];
		for (int pre = 1; pre < dp.length; pre++) {
			dp[pre][0] = 1;
		}

		// 从下往上
		for (int pre = n; pre > 0; pre--) {
			// 从对角线左往右
			for (int rest = pre; rest <= n; rest++) {
				for (int i = pre; i <= rest; i++) {
					dp[pre][rest] += dp[i][rest - i];
				}
			}
		}
		return dp[1][n];
	}

	//=====================================================================

	public static int splitNumber3(int n) {
		if (n < 1) {
			return 0;
		}
		int[][] dp = new int[n + 1][n + 1];

		for (int pre = 1; pre < dp.length; pre++) {
			dp[pre][0] = 1;
		}

		for (int pre = 1; pre < dp.length; pre++) {
			dp[pre][pre] = 1;
		}

		for (int pre = n - 1; pre > 0; pre--) {
			for (int rest = pre + 1; rest <= n; rest++) {
				dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];
			}
		}
		return dp[1][n];
	}

	public static void main(String[] args) {
		int n = 20;
		System.out.println(splitNumber1(n));
		System.out.println(splitNumber2(n));
		System.out.println(splitNumber3(n));
	}
}
